// zoj3209
// 题意：给定一个n*m(n, m<=30)的矩形，现在有p(<=500)个子矩形，
//       问最少用多少个这些子矩形，可以恰好把原来的矩形不重叠的覆盖满。
//
// 题接：精确覆盖，dlx。
//       把原来矩形展开成n*m个点的一维，所有子矩形也类似展开成一维。
//       这样就变成了经典的一维精确覆盖。
//       下面代码每一行是一个子矩形，用双向链表链接。head连接每行的开头。
//
//       每次搜，超过当前答案就退出。然后选重叠元素最小的列来枚举。
//       remove，resume回溯。
//
// run: $exec < input
#include <iostream>

int const maxn = 1000;
int const maxm = maxn * maxn;
int left[maxm], right[maxm], down[maxm], up[maxm];
int col[maxm], row[maxm];
int count_col[maxn];
int head[maxn];
int ans;
int n, m, k;

void init(int n, int m)
{
	for (int i = 0; i <= m; i++) {
		left[i + 1] = i;
		right[i] = i + 1;
		up[i] = down[i] = i;
		count_col[i] = 0;
	}
	for (int i = 1; i <= n; i++) head[i] = -1;
	left[0] = m;
	right[m] = 0;
}

void link(int r, int c, int id)
{
	row[id] = r; col[id] = c;
	up[id] = up[c]; down[up[c]] = id;
	down[id] = c; up[c] = id;
	if (head[r] == -1)
		head[r] = left[id] = right[id] = id;
	else {
		left[id] = left[head[r]];
		right[left[head[r]]] = id;
		left[head[r]] = id;
		right[id] = head[r];
	}
	count_col[c]++;
}

void remove(int c)
{
	right[left[c]] = right[c];
	left[right[c]] = left[c];
	for (int i = down[c]; i != c; i = down[i]) {
		for (int j = right[i]; j != i; j = right[j]) {
			up[down[j]] = up[j];
			down[up[j]] = down[j];
			count_col[col[j]]--;
		}
	}
}

void resume(int c)
{
	right[left[c]] = c;
	left[right[c]] = c;
	for (int i = up[c]; i != c; i = up[i]) {
		for (int j = left[i]; j != i; j = left[j]) {
			up[down[j]] = j;
			down[up[j]] = j;
			count_col[col[j]]++;
		}
	}
}

void dance(int k)
{
	if (ans != -1 && k >= ans) return;
	if (!right[0]) { ans = k; return; }
	int c = right[0];
	for (int i = c; i; i = right[i])
		if (count_col[i] < count_col[c])
			c = i;
	remove(c);
	for (int i = down[c]; i != c; i = down[i]) {
		for (int j = right[i]; j != i; j = right[j])
			remove(col[j]);
		dance(k + 1);
		for (int j = left[i]; j != i; j = left[j])
			resume(col[j]);
	}
	resume(c);
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	while (T--) {
		std::cin >> n >> m >> k;
		init(k, n * m);
		int id = n * m + 1;
		for (int i = 1; i <= k; i++) {
			int x1, y1, x2, y2;
			std::cin >> x1 >> y1 >> x2 >> y2;
			for (int x = x1 + 1; x <= x2; x++)
				for (int y = y1 + 1; y <= y2; y++)
					link(i, y + (x - 1) * m, id++);
		}
		ans = -1;
		dance(0);
		std::cout << ans << '\n';
	}
}

